package com.jojo.elementary.day11_tree;

import com.jojo.elementary.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 *
 * 示例 1：
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 *
 * 示例 2：
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 *
 * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
 */
public class SymmetricTree {

    /** myCode 递归 */
    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        return isEquals(root.left,root.right);
    }

    boolean isEquals(TreeNode left,TreeNode right){
        if (left == null){
            return right == null;
        }
        if (right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        if(!isEquals(left.left,right.right)){
            return false;
        }
        return isEquals(left.right, right.left);
    }

    /** myCode 迭代 */
    public boolean isSymmetric2(TreeNode root) {
        if (root == null || root.left == null && root.right == null){
            return true;
        }
        if (root.left == null || root.right == null){
            return false;
        }
        List<TreeNode> tree = new ArrayList<>();
        tree.add(root.left);
        tree.add(root.right);
        while (!tree.isEmpty()){
            List<TreeNode> temp = new ArrayList<>();
            for (int i = 0;i < tree.size();i = i + 2){
                TreeNode node1 = tree.get(i);
                TreeNode node2 = tree.get(i + 1);
                if (node1 != null && node2 != null){
                    if (node1.val != node2.val){
                        return false;
                    }
                    temp.add(node1.left);
                    temp.add(node2.right);
                    temp.add(node1.right);
                    temp.add(node2.left);
                    continue;
                }
                if (node1 != null || node2 != null){
                    return false;
                }
            }
            tree = temp;
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2,new TreeNode(3),new TreeNode(4));
        root.right = new TreeNode(2,new TreeNode(4),new TreeNode(3));
        SymmetricTree tree = new SymmetricTree();
        System.out.println(tree.isSymmetric2(root));
    }
}
